#include <crt_array.h>
#include <crt_memory.h>

static void array_grow(array_t *a, int min_capacity)
{
	int min_delta = 16;
	int delta;

	/* don't need to grow the capacity of the array */
	if (a->capacity >= min_capacity) {
		return;
	}

	delta = min_capacity;
	/* make delta a multiple of min_delta */
	delta += min_delta - 1;
	delta /= min_delta;
	delta *= min_delta;
	/* actual grow */
	if (delta <= 0) {
		return;
	}

	a->capacity += delta;

	if (a->items == NULL) {
		a->items = (void**)heap_malloc(a->capacity * sizeof(void*));
	}
	else {
		a->items = (void**)heap_realloc(a->items, a->capacity * sizeof(void*));
	}

	/* reset, just in case */
	memset(a->items + a->count, 0,
		(a->capacity - a->count) * sizeof(void *));
}

static int array_pred_insert(array_t *a, int position, void *obj)
{
	int	idx;
	if (position < 0 || position >= a->count) {
		return -1;
	}

	if (a->count >= a->capacity) {
		array_grow(a, a->count + 1);
	}

	for (idx = a->count; idx > position && idx > 0; idx--) {
		a->items[idx] = a->items[idx - 1];
	}
	a->items[position] = obj;
	a->count++;
	return position;
}

static int array_succ_insert(array_t *a, int position, void *obj)
{
	int	idx, position_succ;

	if (position < 0 || position >= a->count) {
		return -1;
	}

	if (a->count >= a->capacity) {
		array_grow(a, a->count + 1);
	}

	position_succ = position + 1;

	for (idx = a->count; idx > position_succ; idx--) {
		a->items[idx] = a->items[idx - 1];
	}
	a->items[position_succ] = obj;
	a->count++;
	return position_succ;
}

static int array_append(array_t *a, void *obj)
{
	if (a->count >= a->capacity) {
		array_grow(a, a->count + 16);
	}
	a->items[a->count++] = obj;
	return a->count - 1;
}

static int array_prepend(array_t *a, void *obj)
{
	return array_pred_insert(a, 0, obj);
}

static int array_push_back(struct array_s *a, void *obj)
{
	return array_append(a, obj);
}

static int array_push_front(struct array_s *a, void *obj)
{
	return array_prepend(a, obj);
}

static void *array_pop_back(struct array_s *a)
{
	void *obj;
	if (a->count <= 0) {
		return NULL;
	}
	a->count--;
	obj = a->items[a->count];
	return obj;
}

static void *array_pop_front(struct array_s *a)
{
	void *obj;
	int   i;

	if (a->count <= 0) {
		return NULL;
	}
	obj = a->items[0];
	a->count--;
	for (i = 0; i < a->count; i++) {
		a->items[i] = a->items[i + 1];
	}

	return obj;
}

static void *array_iter_head(ITER *iter, struct array_s *a)
{
	iter->dlen = -1;
	iter->key = NULL;
	iter->klen = 0;
	iter->i = 0;
	iter->size = a->count;
	if (a->items == NULL || a->count <= 0) {
		iter->ptr = iter->data = 0;
	} else {
		iter->ptr = iter->data = a->items[0];
	}

	return iter->ptr;
}

static void *array_iter_next(ITER *iter, struct array_s *a)
{
	iter->i++;
	if (iter->i >= a->count) {
		iter->data = iter->ptr = 0;
	} else {
		iter->data = iter->ptr = a->items[iter->i];
	}
	return iter->ptr;
}
 
static void *array_iter_tail(ITER *iter, struct array_s *a)
{
	iter->dlen = -1;
	iter->key = NULL;
	iter->klen = 0;
	iter->i = a->count - 1;
	iter->size = a->count;
	if (a->items == NULL || iter->i < 0) {
		iter->ptr = iter->data = 0;
	} else {
		iter->data = iter->ptr = a->items[iter->i];
	}
	return iter->ptr;
}

static void *array_iter_prev(ITER *iter, struct array_s *a)
{
	iter->i--;
	if (iter->i < 0) {
		iter->data = iter->ptr = 0;
	} else {
		iter->data = iter->ptr = a->items[iter->i];
	}
	return iter->ptr;
}

static int array_delete_idx(array_t *a, int position, void (*free_fn)(void *))
{
	int	idx;

	if (position < 0 || position >= a->count) {
		return -1;
	}
	if (free_fn != NULL && a->items[position] != NULL) {
		free_fn(a->items[position]);
	}
	a->items[position] = NULL;   /* sanity set to be null */

	for (idx = position; idx < a->count - 1; idx++) {
		a->items[idx] = a->items[idx + 1];
	}
	a->count--;
	return 0;
}

static int array_delete(array_t *a, int idx, void (*free_fn)(void*))
{
	if (idx < 0 || idx >= a->count) {
		return  -1;
	}
	if (free_fn != NULL && a->items[idx] != NULL) {
		free_fn(a->items[idx]);
	}
	a->count--;
	if (a->count > 0) {
		a->items[idx] = a->items[a->count];
	}
	return 0;
}

static int array_delete_obj(array_t *a, void *obj, void (*free_fn)(void *))
{
	int   idx, position, ret;

	position = -1;
	for (idx = 0; idx < a->count; idx++) {
		if (a->items[idx] == obj) {
			position = idx;
			break;
		}
	}

	if (free_fn != NULL && obj != NULL) {
		free_fn(obj);
	}
	if (position == -1) { /* not found */
		return -1;
	}

	/* don't need to free the obj in array_delete_idx */
	a->items[idx] = NULL;
	ret = array_delete_idx(a, position, NULL);
	if (ret < 0) {
		return -1;
	}
	return ret;
}

static int array_delete_range(array_t *a, int ibegin, int iend,void (*free_fn)(void*))
{
	int   i, imax;

	if (ibegin < 0 || iend < 0 || a->count <= 0) {
		return -1;
	}
	if (ibegin > iend) {
		return -1;
	}

	imax = a->count - 1;
	if (iend > imax) {
		iend = imax;
	}

	if (free_fn != NULL) {
		for (i = ibegin; i <= iend; i++) {
			if (a->items[i] != NULL) {
				free_fn(a->items[i]);
			}
			a->items[i] = NULL;
		}
	}

	a->count -= iend - ibegin + 1;

	for (iend++; iend <= imax;) {
		a->items[ibegin++] = a->items[iend++];
	}

	return 0;
}

static int array_mv_idx(array_t *a, int ito, int ifrom, void (*free_fn)(void *))
{
	int   i, i_obj, i_src, i_max;

	if (ito < 0 || ifrom < 0 || a->count < 0) {
		return -1;
	}

	if (a->count == 0 || ito >= ifrom || ifrom >= a->count) {
		return 0;
	}

	i_obj = ito;
	i_src = ifrom;
	i_max = a->count - 1;

	if (free_fn != NULL) {
		for (i = i_obj; i < i_src; i++) {
			if (a->items[i] != NULL) {
				free_fn(a->items[i]);
			}
			a->items[i] = NULL;
		}
	}
	for (; i_src <= i_max; i_src++) {
		a->items[i_obj] = a->items[i_src];
		i_obj++;
	}

	a->count -= ifrom - ito;
	if (a->count < 0) { /* imposible, sanity check */
		return -1;
	}
	return 0;
}

static void array_pre_append(array_t *a, int app_count)
{
	if (app_count <= 0) {
	}

	if (a->count + app_count > a->capacity) {
		array_grow(a, a->count + app_count);
	}
}

static void* array_index(const array_t *a, int idx)
{
	if (idx < 0 || idx > a->count - 1) {
		return NULL;
	}

	return a->items[idx];
}

static int array_size(const array_t *a)
{
	return a->count;
}


int	array_init(array_t* a, int init_size)
{
	a->count					= 0;
	a->capacity					= 0;
	a->push_back				= array_push_back;
	a->push_front				= array_push_front;

	a->array_pred_insert		= array_pred_insert;
	a->array_succ_insert		= array_succ_insert;

	a->pop_back				= array_pop_back;
	a->pop_front				= array_pop_front;

	a->array_delete_idx			= array_delete_idx;
	a->array_delete			= array_delete;
	a->array_delete_range		= array_delete_range;
	a->array_mv_idx			= array_mv_idx;

	a->iter_head				= array_iter_head;
	a->iter_next				= array_iter_next;
	a->iter_tail				= array_iter_tail;
	a->iter_prev				= array_iter_prev;

	a->array_pre_append			= array_pre_append;
	a->array_index				= array_index;
	a->array_size				= array_size;


	if (init_size <= 0) {
		init_size = 100;
	}

	array_pre_append(a, init_size);
	return 1;
}

void array_clean(array_t *a, void(*free_fn)(void *))
{
	int	idx;

	for (idx = 0; idx < a->count; idx++) {
		if (free_fn != NULL && a->items[idx] != NULL) {
			free_fn(a->items[idx]);
		}
		a->items[idx] = NULL;	/* sanity set to be null */
	}
	a->count = 0;
}

